 #include<cstdio>
 #include<cstdlib>
 #include<cstring>
#include<cmath> 
#define Infp 0x7fffffff
#define Infn 0x80000000
#define DisCon 1000000000
#define MAX  999999999
#define MIN -999999999 
#define Zero(a) memset(a, 0, sizeof(a))
#define Copy(a, b) memcpy(a, b, sizeof(b))
#define Pi acos(-1)
#define FMAX (1E300)
#define FMIN (-1E300)
#define feq(a, b) (fabs((a)-(b))<1E-6)
#define flq(a, b) ((a)<(b)||feq(a, b))
#define RG 1005
const int maxn=110;
 
int a[maxn], b[maxn], f[maxn];
int m, s, c, n, t, l, r;
 
 
void insert(int x, int y)
 {
     while(l<=r&&b[r]<=y)
         r--;
     r++;
     a[r]=x;
     b[r]=y;
 }
int main()
 {
	 int cas;
     scanf("%d",&cas);
	 while(cas--)
	 {
		scanf("%d%d", &t, &n);
		Zero(a);
		Zero(b);
		Zero(f);
	 
		for(int i=1; i<=n; i++)
		{
			 scanf("%d%d%d", &m, &s, &c);
			if(c==0||t/m<c)c=t/m;
			for(int d=0; d<=m-1; d++)
			{
				l=1;r=0;
				for(int j=0; j<=(t-d)/m; j++)
				{
					insert(j, f[j*m+d]-j*s);
					if(a[l]<j-c)l++;
					f[j*m+d]=b[l]+j*s;
				}
			}
		}
		printf("%d\n", f[t]);
	 }
     return 0;
 }
